package leetcode_2001_2100;

import java.net.DatagramPacket;
import java.util.HashSet;
import java.util.Set;

public class LeeCode_2002 {
    public static void main(String[] args) {
        System.out.println(maxProduct("aaaaaaaaaaaa"));
        System.out.println(maxProduct("zqz"));
        System.out.println(maxProduct("tmppdjtm"));
    }
    private static int maxProduct(String s) {
        int n = s.length();
        int[] tab = new int[1 << n];
        int ans = 0;
        for (int i = 1; i < (1 << n); i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0){
                    sb.append(s.charAt(j));
                }
            }
            String tmp = sb.toString();
            int m = tmp.length();
            int res = 1;
            for (int k = 0; k < m; k++) {
                int l = k - 1, r = k + 1, count = 1;
                while (l >= 0 && r < m && tmp.charAt(l) == tmp.charAt(r)){
                    l--;
                    r++;
                    count += 2;
                }
                res = Math.max(res, count);
                if (k + 1 < m && tmp.charAt(k + 1) == tmp.charAt(k)){
                    l = k - 1;
                    r = k + 2;
                    count = 2;
                    while (l >= 0 && r < m && tmp.charAt(l) == tmp.charAt(r)){
                        l--;
                        r++;
                        count += 2;
                    }
                    res = Math.max(res, count);
                }
            }
            tab[i] = res;
        }
        int max = (1 << n) - 1;
        Set<Integer> used = new HashSet<>();
        for (int i = 1; i < (1 << n); i++) {
            if (used.contains(i))
                continue;
            int res = 0;
            int next = i ^ max;
            used.add(i);
            used.add(next);
            for (int k = next; k > 0; k = (k - 1) & next){
                res = Math.max(res, tab[k]);
            }
            ans = Math.max(ans, res * tab[i]);
        }
        return ans;
    }
}